package util

// OrderedListSet 有序(不重复)列表集合
type OrderedListSet[ValueType any] struct {
	lesser func(v1, v2 ValueType) bool
	list   []ValueType
}

// NewOrderedListSet 新建一个有序(不重复)列表集合
func NewOrderedListSet[ValueType any](lesser func(v1, v2 ValueType) bool) (ols *OrderedListSet[ValueType]) {
	return &OrderedListSet[ValueType]{
		lesser: lesser,
		list:   nil,
	}
}

func (ols *OrderedListSet[ValueType]) Insert(newValue ValueType) (exists bool) {
	aim := -1
	for i, value := range ols.list {
		if ols.lesser(value, newValue) {
			aim = i
		} else if !ols.lesser(newValue, value) {
			return true
		}
	}
	ols.list = append(append(ols.list[:aim+1:aim+1], newValue), ols.list[aim+1:]...)
	return false
}

func (ols *OrderedListSet[ValueType]) Length() int {
	return len(ols.list)
}

func (ols *OrderedListSet[ValueType]) Get(pos int) ValueType {
	return ols.list[pos]
}

func (ols *OrderedListSet[ValueType]) GetList() []ValueType {
	return ols.list
}

func (ols *OrderedListSet[ValueType]) Exists(value ValueType) bool {
	if len(ols.list) == 0 {
		return false
	}
	left, right := 0, len(ols.list)-1
	for left < right {
		mid := (left + right + 1) / 2
		if ols.lesser(value, ols.list[mid]) {
			right = mid - 1
		} else {
			left = mid
		}
	}
	return !(ols.lesser(value, ols.list[left]) || ols.lesser(ols.list[left], value))
}

// Merge 合并
func (ols *OrderedListSet[ValueType]) Merge(set *OrderedListSet[ValueType]) {
	for _, value := range set.list {
		ols.Insert(value)
	}
}

// IsEmpty 检查是否为空
func (ols *OrderedListSet[ValueType]) IsEmpty() bool {
	return len(ols.list) == 0
}

// DeepCopy 深拷贝
func (ols *OrderedListSet[ValueType]) DeepCopy() (newOls *OrderedListSet[ValueType]) {
	newOls = NewOrderedListSet[ValueType](ols.lesser)
	newOls.list = make([]ValueType, len(ols.list))
	copy(newOls.list, ols.list)
	return
}

// Delete 删除
func (ols *OrderedListSet[ValueType]) Delete(value ValueType) {
	for i, v := range ols.list {
		if ols.lesser(v, value) {
			continue
		}
		if ols.lesser(value, v) {
			break
		}
		ols.list = append(ols.list[:i], ols.list[i+1:]...)
		return
	}
}
